闘本 2.8 ループの検出

提出

code: txt

import random

class LinkedListNode:

def __init__(self, value, next_node=None, prev_node=None):

self.value = value

self.next = next_node

self.prev = prev_node

def __str__(self):

return str(self.value)

class LinkedList:

def __init__(self, values=None):

self.head = None

self.tail = None

if values is not None:

self.add_multiple(values)

def __iter__(self):

current = self.head

while current:

yield current

current = current.next

def __str__(self):

return " -> ".join(values)

def __len__(self):

result = 0

node = self.head

while node:

result += 1

node = node.next

return result

def values(self):

def add(self, value):

if self.head is None:

self.tail = self.head = LinkedListNode(value)

else:

self.tail.next = LinkedListNode(value)

self.tail = self.tail.next

return self.tail

def add_to_beginning(self, value):

if self.head is None:

self.tail = self.head = LinkedListNode(value)

else:

self.head = LinkedListNode(value, self.head)

return self.head

def add_multiple(self, values):

for v in values:

self.add(v)

@classmethod

def generate(cls, k, min_value, max_value):

return cls(random.choices(range(min_value, max_value), k=k))

class DoublyLinkedList(LinkedList):

def add(self, value):

if self.head is None:

self.tail = self.head = LinkedListNode(value)

else:

self.tail.next = LinkedListNode(value, None, self.tail)

self.tail = self.tail.next

return self

def find_loop(ll):

current = ll.head

visited = set()

while ll:

node = ll.next

if node.value in visited:

return node

else:

visited.add(node.value)

メモ